package leetcode101.ch3;

import java.util.Collections;
import java.util.Comparator;
import java.util.List;

//LC 524
public class FindLongestSubStr {
    public String findLongestWord(String s, List<String> dictionary) {
        Collections.sort(dictionary, new Comparator<String>(){
            @Override
            public int compare(String s1, String s2) {
                if (s1.length() == s2.length()){
                    return s1.compareTo(s2);
                }else {
                    //长的排前面
                    return s2.length() - s1.length();
                }
            }
        });
        for (int i = 0; i < dictionary.size(); i++) {
            String s1 = dictionary.get(i);
            if (isSubStr(s, s1)){
                return s1;
            }
        }
        return "";
    }

    private boolean isSubStr(String s1, String s2) {
        int i1 = 0, i2 = 0;
        while(i1 < s1.length() && i2 < s2.length()) {
            if (s1.charAt(i1) == s2.charAt(i2)){
                i1++;
                i2++;
            }else {
                i1++;
            }
        }
        return i2 == s2.length();
    }
}
